package com.javabasic.algorithm.sword_of_offer;

import java.util.HashMap;

/**
 * @author mir.xiong
 * @version 1.0
 * @description
 * @see
 * @since Created by work on 2022/1/6 11:25 下午
 */
public class 剑指_Offer_35_复杂链表的复制 {

    /**
     * 深复制链表 next指针+random指针
     * @param head
     * @return
     */
    public NodeOffer35 copyRandomList(NodeOffer35 head) {
        if (head == null) {
            return head;
        }

        NodeOffer35 fakeHead = new NodeOffer35(-1), newFakeHead = new NodeOffer35(-1);
        fakeHead.next = head;
        NodeOffer35 temp = fakeHead, newTemp = newFakeHead, newNodeOffer35;

        /**
         * 记录旧节点与新节点的对应关系
         */
        HashMap<NodeOffer35, NodeOffer35> oldToNew = new HashMap<>(8);

        while (temp.next != null) {
            temp = temp.next;
            newNodeOffer35 = new NodeOffer35(temp.val);
            newTemp.next = newNodeOffer35;
            newTemp = newNodeOffer35;
            oldToNew.put(temp, newNodeOffer35);
        }

        temp = fakeHead;
        newTemp = newFakeHead;
        while (temp.next != null) {
            temp = temp.next;
            newTemp = newTemp.next;
            newTemp.random = oldToNew.getOrDefault(temp.random,null);
        }

        return newFakeHead.next;
    }
}
class NodeOffer35 {
    int val;
    NodeOffer35 next;
    NodeOffer35 random;

    public NodeOffer35(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}